#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

//边节点类的实现 初始化边的终点和链接
EdgeNode::EdgeNode() : dest(-1),link(nullptr) {}

EdgeNode::EdgeNode(int dest, EdgeNode* link) : dest(dest),link(link) {}

EdgeNode::~EdgeNode() {}

int EdgeNode::getDest(){    //获取边的终点
    return dest;
}

EdgeNode* EdgeNode::getNext(){      //获取下一个边节点
    return link;
}

void EdgeNode::setDest(int dest){   //设置边终点
    this->dest=dest;
}

void EdgeNode::setNext(EdgeNode* link){     //设置下一个边节点
    this->link=link;
}

//顶点节点类的实现 初始化顶点数据和边链表
VertexNode::VertexNode() : data('\0'),firstEdge(nullptr) {}

VertexNode::VertexNode(char data, EdgeNode* firstEdge) : data(data),firstEdge(firstEdge) {}

VertexNode::~VertexNode(){
    while(firstEdge)
    {
        EdgeNode* temp=firstEdge;
        firstEdge=firstEdge->getNext();
        delete temp;
    }
}

char VertexNode::getData(){     //获取顶点数据
    return data;
}

EdgeNode* VertexNode::getFirstEdge(){       //获取第一个边节点
    return firstEdge;
}

void VertexNode::setData(char data){        //设置顶点数据
    this->data=data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge){     //设置第一个边节点
    this->firstEdge=firstEdge;
}

//图类的实现
MyGraph::MyGraph() : nodeNum(0),edgeNum(0),VexList(nullptr) {}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList){
    this->nodeNum=nodeNum;
    this->edgeNum=edgeNum;
    VexList= new VertexNode[nodeNum];

    //将顶点初始化
    for(int i=0;i<nodeNum;i++)
    {
        VexList[i].setData(nodeList[i]);
        VexList[i].setFirstEdge(nullptr);
    }

    //创建边节点
    for(int i=0;i<edgeNum;i++)
    {
        int start=edgeStartList[i];     //边起点
        int end=edgeEndList[i];         //边终点

        //在链表头插入边节点 无向图双向插入
        EdgeNode* newEdge1=new EdgeNode(end,VexList[start].getFirstEdge());
        VexList[start].setFirstEdge(newEdge1);      //新边插入起点的边链表中

        EdgeNode* newEdge2=new EdgeNode(start,VexList[end].getFirstEdge());
        VexList[end].setFirstEdge(newEdge2);        //新边插入终点的边链表中
    }
}

MyGraph::~MyGraph(){
    delete[] VexList;
}

int MyGraph::getNodeNum(){
    return nodeNum;     //返回顶点数目
}

int MyGraph::getEdgeNum(){
    return edgeNum;     //返回边数
}

//打印图的邻接表
string MyGraph::printGraph(){
    stringstream result;
    for(int i=0;i<nodeNum;++i)
    {
        result<<VexList[i].getData()<<":";
        EdgeNode* edge=VexList[i].getFirstEdge();
        while(edge)
        {
            result<<" "<<VexList[edge->getDest()].getData();
            edge=edge->getNext();
        }
        result<<"\n";
    }
    string output=result.str();
    return output.substr(0,output.size()-1);
}

//获取第一个邻接顶点
int MyGraph::getFirstNeighbor(int v, int* visited){
    EdgeNode* edge=VexList[v].getFirstEdge();   //获取顶点v的第一个边节点
    return edge?edge->getDest():-1;
}

//获取下一个邻接顶点
int MyGraph::getNextNeighbor(int v, int w, int* visited){
    EdgeNode* edge=VexList[v].getFirstEdge();   //获取顶点v的第一个边节点
    while(edge)
    {
        if(edge->getDest()==w)      //找到当前邻接顶点w
        {
            edge=edge->getNext();
            return edge?edge->getDest():-1;     //返回w的下一个邻接顶点
        }
        edge=edge->getNext();
    }
    return -1;
}

//图的深度优先搜索
void MyGraph::DFS(int v, int* visited, string& result){
    visited[v]=1;   //将当前定点标记为已访问
    result+=VexList[v].getData();       //当前顶点加入至结果字符串
    result+=" ";
    EdgeNode* edge=VexList[v].getFirstEdge();   //获取当前节点的第一个边节点
    while(edge)
    {
        int dest=edge->getDest();   //获取邻接顶点
        if(!visited[dest])
        {
            DFS(dest,visited,result);   //递归访问邻接顶点
        }
        edge=edge->getNext();
    }
}

//执行DFS遍历并返回结果字符串
string MyGraph::graph_DFS_Traverse(){
    int* visited=new int[nodeNum]();    //创建访问标记数组并初始化为0
    string result;
    for(int i=0;i<nodeNum;i++)
    {
        if(!visited[i])
        {
            DFS(i,visited,result);      //从顶点开始调用DFS
        }
    }
    delete[] visited;
    return result;
}

//图的广度优先搜索
void MyGraph::BFS(int v, int* visited, string& result){
    queue<int> q;
    visited[v]=1;       //标记当前节点为已访问
    q.push(v);          //当前节点入队
    while(!q.empty())
    {
        int current=q.front();      //获取队首元素
        q.pop();
        result+=VexList[current].getData(); //当前节点添加至结果字符串
        result+=" ";
        EdgeNode* edge=VexList[current].getFirstEdge();     //获取当前顶点的第一个边节点
        while(edge)
        {
            int dest=edge->getDest();   //获取邻接顶点
            if(!visited[dest])
            {
                visited[dest]=1;
                q.push(dest);           //邻接顶点入队
            }
            edge=edge->getNext();
        }
    }
}

//执行BFS遍历并返回字符串
string MyGraph::graph_BFS_Traverse(){
    int* visited=new int[nodeNum]();
    string result;
    for(int i=0;i<nodeNum;i++)
    {
        if(!visited[i])
        {
            BFS(i,visited,result);      //从顶点开始调用BFS
        }
    }
    delete[] visited;
    return result;
}
